package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

/**
 * @author Dennis Li
 * @date 2020/9/14 22:07
 */
public class ReverseKGroup_25 {

    public static void main(String[] args) {
        ListNode dummy = new ListNode(-1), cur = dummy;
        for (int i = 0; i < 5; i++) {
            cur.next = new ListNode(i + 1);
            cur = cur.next;
        }
        ReverseKGroup_25 ans = new ReverseKGroup_25();
        ans.reverseKGroup(dummy.next, 2);
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) return head;
        ListNode dummyHead = new ListNode(-1), pre = dummyHead;
        ListNode cur = head;

        // 计算总的长度
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }

        // lEN / K 代表要翻转多少次
        for (int i = 0; i < len / k; i++) {
            pre.next = reverseN(head, k);
            // pre用于连接链表
            pre = prev;
            head = successor;
        }

        return dummyHead.next;
    }

    ListNode successor, prev;

    // 翻转N个结点的经典实现
    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode node = reverseN(head.next, n - 1);
        head.next.next = head;
        // 翻转完成后successor指向这一段翻转链表尾结点的下一个结点
        // 即和正常链条想链接的那个点
        head.next = successor;
        // 这里维护一个前驱指针，翻转完成后，prev指向这一段翻转链表的尾结点
        prev = head;
        return node;
    }

}
